Fast Exact Shortest Path and Distance Queries on Road Networks with Parametrized Costs

摘要

We study a scenario for route planning in road networks, where the objectiveto be optimized may change between every shortest path query. Since thisinvalidates many of the known speedup techniques for road networks that arebased on preprocessing of shortest path structures, we investigateoptimizations exploiting solely the topological structure of networks. Weexperimentally evaluate our technique on a large set of real-world roadnetworks of various data sources. With lightweight preprocessing our techniqueanswers long-distance queries across continental networks significantly fasterthan previous approaches towards the same problem formulation.